{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Out of Boundary Paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findPaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #出界的路径数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的网格和一个球。球的起始坐标为 <code>[startRow, startColumn]</code> 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 <strong>最多</strong> 可以移动 <code>maxMove</code> 次球。</p>\n",
    "\n",
    "<p>给你五个整数 <code>m</code>、<code>n</code>、<code>maxMove</code>、<code>startRow</code> 以及 <code>startColumn</code> ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 后的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/28/out_of_boundary_paths_1.png\" style=\"width: 500px; height: 296px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/28/out_of_boundary_paths_2.png\" style=\"width: 500px; height: 293px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1\n",
    "<strong>输出：</strong>12\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;= maxMove &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;= startRow &lt; m</code></li>\n",
    "\t<li><code>0 &lt;= startColumn &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [out-of-boundary-paths](https://leetcode.cn/problems/out-of-boundary-paths/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [out-of-boundary-paths](https://leetcode.cn/problems/out-of-boundary-paths/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n2\\n2\\n0\\n0', '1\\n3\\n3\\n0\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # 方法2、bfs\n",
    "        MOD = int(1e9 + 7)\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        # 换种写法————BFS + 记录到达每个点的路径数量\n",
    "        pos = {(startRow,startColumn):1}\n",
    "        res = 0\n",
    "        for i in range(maxMove):\n",
    "            cnt = defaultdict(int)\n",
    "            for x,y in pos.keys():\n",
    "                for x0,y0 in directions:\n",
    "                    if 0 <= x + x0 < m and 0 <= y + y0 < n:\n",
    "                        cnt[(x+x0,y+y0)] += pos[(x,y)]\n",
    "                    else:\n",
    "                        res += pos[(x, y)]\n",
    "            pos = cnt\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)  #通过修饰器实现记忆化\n",
    "    def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:\n",
    "        count = 0\n",
    "        if N < 0:\n",
    "            return count\n",
    "        if i < 0 or i >= m or j < 0 or j >= n:\n",
    "            return 1\n",
    "        for di, dj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "            count = (count + self.findPaths(m, n, N-1, di, dj)) % 1000000007\n",
    "        return count\n",
    "\n",
    "# 作者：Harmon Jiang\n",
    "# 链接：https://leetcode.cn/problems/out-of-boundary-paths/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        outCounts = 0\n",
    "        dp = [[[0] * n for _ in range(m)] for _ in range(maxMove + 1)]\n",
    "        dp[0][startRow][startColumn] = 1\n",
    "        for i in range(maxMove):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    if dp[i][j][k] > 0:\n",
    "                        for j1, k1 in [(j - 1, k), (j + 1, k), (j, k - 1), (j, k + 1)]:\n",
    "                            if 0 <= j1 < m and 0 <= k1 < n:\n",
    "                                dp[i + 1][j1][k1] = (dp[i + 1][j1][k1] + dp[i][j][k]) % MOD\n",
    "                            else:\n",
    "                                outCounts = (outCounts + dp[i][j][k]) % MOD\n",
    "        \n",
    "        return outCounts\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        outCounts = 0\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[startRow][startColumn] = 1\n",
    "        for i in range(maxMove):\n",
    "            dpNew = [[0] * n for _ in range(m)]\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    if dp[j][k] > 0:\n",
    "                        for j1, k1 in [(j - 1, k), (j + 1, k), (j, k - 1), (j, k + 1)]:\n",
    "                            if 0 <= j1 < m and 0 <= k1 < n:\n",
    "                                dpNew[j1][k1] = (dpNew[j1][k1] + dp[j][k]) % MOD\n",
    "                            else:\n",
    "                                outCounts = (outCounts + dp[j][k]) % MOD\n",
    "            dp = dpNew\n",
    "        \n",
    "        return outCounts\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/out-of-boundary-paths/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        dp = [[0]*(n+2) for _ in range(m+2)]\n",
    "        for i in range(n+2):\n",
    "            dp[0][i] = 1\n",
    "            dp[m+1][i] = 1\n",
    "        for i in range(m+2):\n",
    "            dp[i][0] = 1\n",
    "            dp[i][n+1] = 1\n",
    "        while maxMove:\n",
    "            nex = copy.deepcopy(dp)\n",
    "            for i in range(1,m+1):\n",
    "                for j in range(1,n+1):\n",
    "                    nex[i][j] = (dp[i-1][j]+dp[i+1][j]+dp[i][j-1]+dp[i][j+1])%mod\n",
    "            dp = nex\n",
    "            maxMove -= 1\n",
    "        return dp[startRow+1][startColumn+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        if maxMove==0:\n",
    "            return 0\n",
    "        mod = 10**9+7\n",
    "        distance = [[0]*n for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            distance[i][0]+=1\n",
    "            distance[i][-1] += 1\n",
    "        for j in range(n):\n",
    "            distance[0][j]+=1\n",
    "            distance[-1][j]+=1\n",
    "        res = distance[startRow][startColumn]\n",
    "        for k in range(1,maxMove):\n",
    "            temp = [[0]*n for _ in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i>0:\n",
    "                        temp[i][j] += distance[i-1][j]\n",
    "                    if i<m-1:\n",
    "                        temp[i][j] += distance[i+1][j]\n",
    "                    if j>0:\n",
    "                        temp[i][j] += distance[i][j-1]\n",
    "                    if j<n-1:\n",
    "                        temp[i][j] += distance[i][j+1]\n",
    "            distance = [[num for num in nums] for nums in temp]\n",
    "            res = (res+distance[startRow][startColumn])%mod\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\r\n",
    "        if maxMove == 0:\r\n",
    "            return 0\r\n",
    "        dp0 = [[0] * n for _ in range(m)]\r\n",
    "        dp0[startRow][startColumn] = 1\r\n",
    "        dp1 = [[0] * n for _ in range(m)]\r\n",
    "        rst = [[0] * n for _ in range(m)]\r\n",
    "        rst[startRow][startColumn] = 1\r\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\r\n",
    "        for _ in range(maxMove-1):\r\n",
    "            for i in range(m):\r\n",
    "                for j in range(n):\r\n",
    "                    dp1[i][j] = sum(dp0[i+di][j+dj] for di, dj in directions if 0 <= i+di < m and 0 <= j+dj < n) % (10**9 + 7)\r\n",
    "                    rst[i][j] += dp1[i][j]\r\n",
    "                    rst[i][j] %= (10**9 + 7)\r\n",
    "            dp0, dp1 = dp1, dp0\r\n",
    "        rst = sum(rst[0]) % (10**9 + 7) + sum(rst[-1]) % (10**9 + 7) \\\r\n",
    "                + sum([rst[i][0] for i in range(m)]) % (10**9 + 7) \\\r\n",
    "                + sum([rst[i][-1] for i in range(m)]) % (10**9 + 7)\r\n",
    "        return rst % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        dp = [[[0] * n for _ in range(m)] for _ in range(maxMove+1)]  # dp[i][j][k] 经过 i 步之后，落在 mat[j][k] 处的路径数量\n",
    "        dp[0][startRow][startColumn] = 1\n",
    "\n",
    "        for i in range(maxMove):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    if dp[i][j][k] > 0:\n",
    "                        for j1, k1 in [(j-1, k), (j+1, k), (j, k-1), (j, k+1)]:\n",
    "                            if 0 <= j1 < m and 0 <= k1 < n:\n",
    "                                dp[i+1][j1][k1] = (dp[i+1][j1][k1] + dp[i][j][k]) % MOD\n",
    "                            else:\n",
    "                                ans = (ans + dp[i][j][k]) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        memo=[[[-1 for _ in range(maxMove+1)] for _ in range(n)] for _ in range(m)]\n",
    "        def dfs(m,n,moveCount,i,j,memo):\n",
    "            if i<0 or j<0 or i>=m or j>=n:\n",
    "                return 1\n",
    "            if moveCount==0:\n",
    "                return 0\n",
    "            print(len(memo),len(memo[0]),len(memo[0][0]))\n",
    "            print(i,j,moveCount)\n",
    "            if memo[i][j][moveCount]!=-1:\n",
    "                return memo[i][j][moveCount]\n",
    "            if i-moveCount>=0 and j-moveCount>=0 and i+moveCount<m and j+ moveCount<n:\n",
    "                return 0\n",
    "            sum=0\n",
    "            for di,dj in ((-1,0),(0,1),(1,0),(0,-1)):\n",
    "                sum=(sum+dfs(m,n,moveCount-1,i+di,j+dj,memo))%MOD\n",
    "            memo[i][j][moveCount]=sum\n",
    "            return sum\n",
    "        return dfs(m,n,maxMove,startRow,startColumn,memo)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        if m == 1 and n == 1:\n",
    "            return 4\n",
    "        if maxMove == 0:\n",
    "            return 0\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m-1:\n",
    "                    if m == 1:\n",
    "                        dp[i][j] = 2\n",
    "                    else:\n",
    "                        dp[i][j] = 1\n",
    "                elif j == 0 or j == n-1:\n",
    "                    if n == 1:\n",
    "                        dp[i][j] = 2\n",
    "                    else:\n",
    "                        dp[i][j] = 1\n",
    "        if m == 1 or n == 1:\n",
    "            dp[0][n-1] = 2\n",
    "            dp[m-1][0] = 2\n",
    "            dp[m-1][n-1] = 3\n",
    "            dp[0][0] = 3\n",
    "        else:\n",
    "            dp[0][0] = 2\n",
    "            dp[0][n-1] = 2\n",
    "            dp[m-1][0] = 2\n",
    "            dp[m-1][n-1] = 2\n",
    "        sumpath = dp[startRow][startColumn]\n",
    "        for lest in range(1, maxMove):\n",
    "            temp_dp = copy.deepcopy(dp)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if m-1 > i > 0 and n-1 > j > 0:\n",
    "                        dp[i][j] = temp_dp[i+1][j] + temp_dp[i-1][j] + temp_dp[i][j+1] + temp_dp[i][j-1]\n",
    "                    elif i == 0 and j == 0:\n",
    "                        if m == 1 and n != 1:\n",
    "                            dp[i][j] = temp_dp[i][j + 1]\n",
    "                        elif m != 1 and n == 1:\n",
    "                            dp[i][j] = temp_dp[i + 1][j]\n",
    "                        else:\n",
    "                            dp[i][j] = temp_dp[i+1][j] + temp_dp[i][j+1]\n",
    "                    elif i == 0 and j == n-1:\n",
    "                        if m == 1 and n != 1:\n",
    "                            dp[i][j] = temp_dp[i][j - 1]\n",
    "                        else:\n",
    "                            dp[i][j] = temp_dp[i+1][j] + temp_dp[i][j-1]\n",
    "                    elif i == m-1 and j == 0:\n",
    "                        if m != 1 and n == 1:\n",
    "                            dp[i][j] = temp_dp[i - 1][j]\n",
    "                        else:\n",
    "                            dp[i][j] = temp_dp[i-1][j] + temp_dp[i][j+1]\n",
    "                    elif i == m-1 and j == n-1:\n",
    "                        dp[i][j] = temp_dp[i-1][j] + temp_dp[i][j-1]\n",
    "\n",
    "                    elif i == 0:\n",
    "                        if m == 1 and n != 1:\n",
    "                            dp[i][j] = temp_dp[i][j + 1] + temp_dp[i][j - 1]\n",
    "                        else:\n",
    "                            dp[i][j] = temp_dp[i+1][j] + temp_dp[i][j+1] + temp_dp[i][j-1]\n",
    "                    elif j == n-1:\n",
    "                        if m != 1 and n == 1:\n",
    "                            dp[i][j] = temp_dp[i + 1][j] + temp_dp[i - 1][j]\n",
    "                        else:\n",
    "                            dp[i][j] = temp_dp[i+1][j] + temp_dp[i-1][j] + temp_dp[i][j-1]\n",
    "                    elif i == m-1:\n",
    "                        if m == 1 and n != 1:\n",
    "                            dp[i][j] = temp_dp[i][j + 1] + temp_dp[i][j - 1]\n",
    "                        else:\n",
    "                            dp[i][j] = temp_dp[i-1][j] + temp_dp[i][j+1] + temp_dp[i][j-1]\n",
    "                    elif j == 0:\n",
    "                        if m != 1 and n == 1:\n",
    "                            dp[i][j] = temp_dp[i + 1][j] + temp_dp[i - 1][j]\n",
    "                        else:\n",
    "                            dp[i][j] = temp_dp[i-1][j] + temp_dp[i+1][j] + temp_dp[i][j+1]\n",
    "                    print(dp[i][j], i, j)\n",
    "                    if i == startRow and j == startColumn:\n",
    "                        sumpath+=dp[i][j]\n",
    "\n",
    "        return sumpath % 1000000007\n",
    "\n",
    "# dp[i][j][move]: 在[i][j]位置，剩余move步数，能移出界外的路径数\n",
    "# dp[i][j][move] = dp[i+1][j][move-1] + dp[i-1][j][move-1] + dp[i][j+1][move-1] + dp[i][j-1][move-1]\n",
    "# 当move =2时，上下左右移动一步，到达的点，在只剩一步时，能移动到界外的路径数。其总和就是在[i][j][2]时，能移动到界外的路径数\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # 暴力递归\n",
    "        \n",
    "        # def recrusive(m,n,max_move,row,col):\n",
    "        #     if max_move < 0:\n",
    "        #         return 0\n",
    "        #     if max_move >= 0 and (row < 0 or row > m-1 or col < 0 or col > n-1):\n",
    "        #         return 1\n",
    "        #     ans = 0\n",
    "        #     ans += recrusive(m,n,max_move-1,row-1,col) # 往上\n",
    "        #     ans += recrusive(m,n,max_move-1,row+1,col) # 往下\n",
    "        #     ans += recrusive(m,n,max_move-1,row,col-1) # 往左\n",
    "        #     ans += recrusive(m,n,max_move-1,row,col+1) # 往右\n",
    "        #     return ans % (1e9+7)\n",
    "\n",
    "        # return recrusive(m,n,maxMove,startRow,startColumn)\n",
    "\n",
    "        # 记忆化搜索，某一个位置可以从它的上下左右到达它，所以可以用一个dp数组保存当前位置\n",
    "        # 剩余x步时，将球移除边界的路径数量\n",
    "        # dp = [[[-1]*(maxMove+1) for _ in range(n)] for _ in range(m)]  # dp[i][j][k]表示小球在位置[i,j]，剩余移动次数为k时，将球移出边界的路径数量\n",
    "        # def recrusive(m,n,max_move,row,col):\n",
    "        #     nonlocal dp\n",
    "        #     if max_move < 0:\n",
    "        #         return 0\n",
    "        #     if max_move >= 0 and (row < 0 or row > m-1 or col < 0 or col > n-1):\n",
    "        #         return 1\n",
    "        #     if dp[row][col][max_move] != -1:\n",
    "        #         return dp[row][col][max_move]\n",
    "        #     ans = 0\n",
    "        #     ans += recrusive(m,n,max_move-1,row-1,col) # 往上\n",
    "        #     ans += recrusive(m,n,max_move-1,row+1,col) # 往下\n",
    "        #     ans += recrusive(m,n,max_move-1,row,col-1) # 往左\n",
    "        #     ans += recrusive(m,n,max_move-1,row,col+1) # 往右\n",
    "        #     dp[row][col][max_move] = ans % (1e9+7)\n",
    "        #     return dp[row][col][max_move]\n",
    "        # return recrusive(m,n,maxMove,startRow,startColumn) % (1e9+7)\n",
    "\n",
    "        # 动态规划\n",
    "        # 1、确定dp数组的下标及含义\n",
    "        # dp[i][j][k]表示小球移动i次之后位于坐标(j,k)的路径数量\n",
    "        # 2、确定递推公式\n",
    "        # 我们知道\n",
    "        # 3、初始化dp数组\n",
    "        # 初始化边界条件dp[0][startRow][startColumn] = 1，因为不需要移动就在初始位置了，初始化dp[0][j][k]=0，其中j、k不等于startRow、startColumn\n",
    "        # 4、确定遍历顺序\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        outCounts = 0\n",
    "        dp = [[[0]*n for _ in range(m)] for _ in range(maxMove+1)]\n",
    "        dp[0][startRow][startColumn] = 1\n",
    "        for i in range(maxMove):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    if dp[i][j][k] > 0:\n",
    "                        for j1,k1 in [(j-1,k),(j+1,k),(j,k-1),(j,k+1)]:\n",
    "                            if 0 <= j1 < m and 0 <= k1 < n:\n",
    "                                dp[i+1][j1][k1] = (dp[i+1][j1][k1]+dp[i][j][k]%mod)\n",
    "                            else:\n",
    "                                outCounts = (outCounts+dp[i][j][k]) % mod\n",
    "        return outCounts\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[[0] * (n + 2) for _ in range(m + 2)] for k in range(maxMove + 1)]\n",
    "        dp[0][startRow + 1][startColumn + 1] = 1\n",
    "        ans = 0\n",
    "\n",
    "        for k in range(1, maxMove + 1):\n",
    "            for i in range(m + 2):\n",
    "                for j in range(n + 2):\n",
    "                    up = dp[k - 1][i - 1][j] if i > 1 and (j > 0 and j < n + 1) else 0\n",
    "                    down = dp[k - 1][i + 1][j] if i < m and (j > 0 and j < n + 1) else 0\n",
    "                    left = dp[k - 1][i][j - 1] if j > 1 and (i > 0 and i < m + 1) else 0\n",
    "                    right = dp[k - 1][i][j + 1] if j < n and (i > 0 and i < m + 1) else 0\n",
    "                    dp[k][i][j] = (up + down + left + right) % MOD\n",
    "                    if i == 0 or i == m + 1 or j == 0 or j == n + 1:\n",
    "                        ans = (ans + dp[k][i][j]) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # 动态规划。dynamic programming，my own solution\n",
    "        h = m + 2\n",
    "        l = n + 2\n",
    "        # dp: 从 start 正好用 k 步 到 边界外 的path 个数。最后 要 aggregate 从 0 步 到 maxMove 步 所有可能到达 边界外 的path 个数\n",
    "        # 把边界外面的点 扩充成 dp 的 一部分\n",
    "        dp = [[[0 for _ in range(maxMove + 1)] for _ in range(l)] for _ in range(h)]\n",
    "        dp[startRow + 1][startColumn + 1][0] = 1\n",
    "        for k in range(1, maxMove + 1):\n",
    "            for i in range(h):\n",
    "                for j in range(l):\n",
    "                    if ((i == 0 or i == h - 1) and (j == 0 or j == l - 1)):\n",
    "                        continue\n",
    "                    paths = 0\n",
    "                    if i > 1 and j != 0 and j != l - 1:\n",
    "                        paths += dp[i - 1][j][k - 1]\n",
    "                    if j > 1 and i != 0 and i != h - 1:\n",
    "                        paths += dp[i][j - 1][k - 1]\n",
    "                    if i + 1 < h - 1 and j != 0 and j != l - 1:\n",
    "                        paths += dp[i + 1][j][k - 1]\n",
    "                    if j + 1 < l - 1 and i != 0 and i != h - 1:\n",
    "                        paths += dp[i][j + 1][k - 1]\n",
    "                    dp[i][j][k] = paths\n",
    "        res = 0\n",
    "        #print(dp)\n",
    "        for k in range(maxMove + 1):\n",
    "            for i in range(h):\n",
    "                for j in range(l):\n",
    "                    if ((i == 0 or i == h - 1) and j != 0 and j != l - 1) or\\\n",
    "                            ((j == 0 or j == l - 1) and i != 0 and i != h - 1):\n",
    "                        res += dp[i][j][k]\n",
    "        '''\n",
    "        # debug\n",
    "        for k in range(maxMove + 1):\n",
    "            print('moves: {}'.format(k))\n",
    "            for i in range(h):\n",
    "                debug_line = ''\n",
    "                for j in range(l):\n",
    "                    debug_line += str(dp[i][j][k]) + '\\t'\n",
    "                print(debug_line) \n",
    "        '''\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def DFS(self,m,n,startRow,startColumn,op,maxMove,memo):\n",
    "        if op>maxMove:\n",
    "            return 0\n",
    "        if startRow<0 or startRow>=m or startColumn<0 or startColumn>=n:\n",
    "            return 1\n",
    "        if memo[startRow][startColumn][op]!=-1:\n",
    "            return memo[startRow][startColumn][op]\n",
    "        \n",
    "        # 剪枝：如果小球不管怎么移动都无法越出网格，那就剪掉这个枝\n",
    "        if startRow + (maxMove-op) < m and startRow - (maxMove-op) >= 0 and \\\n",
    "            startColumn + (maxMove-op) < n and startColumn - (maxMove-op) >=0 :\n",
    "                return 0\n",
    "       \n",
    "\n",
    "\n",
    "        \n",
    "        cnt = 0\n",
    "        cnt = (cnt+ self.DFS(m,n,startRow+1,startColumn,op+1,maxMove,memo))%(pow(10,9)+7)\n",
    "        cnt = (cnt+ self.DFS(m,n,startRow-1,startColumn,op+1,maxMove,memo))%(pow(10,9)+7)\n",
    "        cnt = (cnt+ self.DFS(m,n,startRow,startColumn+1,op+1,maxMove,memo))%(pow(10,9)+7)\n",
    "        cnt = (cnt+ self.DFS(m,n,startRow,startColumn-1,op+1,maxMove,memo))%(pow(10,9)+7)\n",
    "        \n",
    "        \n",
    "        memo[startRow][startColumn][op] = cnt if cnt!=0 else -1\n",
    "        return cnt\n",
    "            \n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        res = [0]\n",
    "        memo = [[[-1]*(maxMove+1) for j in range(n)] for i in range(m)]\n",
    "\n",
    "        # print(memo)\n",
    "        self.DFS(m,n,startRow,startColumn,0,maxMove,memo)\n",
    "        # print(memo)\n",
    "        res = memo[startRow][startColumn][0] if memo[startRow][startColumn][0]!=-1 else 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        outCounts = 0\n",
    "        dp = [[[0] * n for _ in range(m)] for _ in range(maxMove + 1)]\n",
    "        dp[0][startRow][startColumn] = 1\n",
    "        for k in range(maxMove):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if dp[k][i][j] > 0: #可以不判断，但是会做很多无效的遍历； 1。count > 0表示当前位置可以到达，可以到达的上下左右移动才有意义；如果不判断的话，相当于不可到达的位置也进行上下左右移动，相邻位置计算路径时加的是0，这样是没有意义的\n",
    "                        for i1, j1 in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                            if 0 <= i1 < m and 0 <= j1 < n:\n",
    "                                dp[k + 1][i1][j1] = (dp[k + 1][i1][j1] + dp[k][i][j]) % MOD\n",
    "                            else:\n",
    "                                outCounts = (outCounts + dp[k][i][j]) % MOD\n",
    "        return outCounts\n",
    "\n",
    "# 可以优化， 每个点只与k - 1层有关 可优化成 m * n * 2\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        outCounts = 0\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[startRow][startColumn] = 1\n",
    "        for i in range(maxMove):\n",
    "            dpNew = [[0] * n for _ in range(m)] #保存第i-1步的结果\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    if dp[j][k] > 0:    #对于每个点，如果该点为0，则说明在当前步数下没有能到达该点的路径，不用管\n",
    "                        for j1, k1 in [(j - 1, k), (j + 1, k), (j, k - 1), (j, k + 1)]:\n",
    "                            if 0 <= j1 < m and 0 <= k1 < n:\n",
    "                                dpNew[j1][k1] = (dpNew[j1][k1] + dp[j][k]) % MOD\n",
    "                            else:\n",
    "                                outCounts = (outCounts + dp[j][k]) % MOD\n",
    "            dp = dpNew\n",
    "        return outCounts\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        ans = 0\n",
    "        dp = [[0]*n for i in range(m)]\n",
    "        dp[startRow][startColumn] = 1\n",
    "        for k in range(maxMove):\n",
    "            cur = [[0]*n for i in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if dp[i][j] != 0:\n",
    "                        for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                            if x >= m or x < 0 or y >= n or y < 0:\n",
    "                                ans += dp[i][j]\n",
    "                            else:\n",
    "                                cur[x][y] += dp[i][j]\n",
    "            ans %= 10 ** 9 + 7\n",
    "            dp = cur\n",
    "        return ans\n",
    "# 记忆化搜索\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.MOD = int(1e9+7)\n",
    "        self.dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "    def findPaths(self, m: int, n: int, max: int, r: int, c: int) -> int:\n",
    "        cache = [[[-1] * (max + 1) for _ in range(n)] for _ in range(m)]\n",
    "        return self.dfs(m, n, max, r, c, cache)\n",
    "    def dfs(self, m: int, n: int, max: int, x: int, y: int, cache: List[List[List[int]]]) -> int:\n",
    "        if x < 0 or x >= m or y < 0 or y >= n:\n",
    "            return 1\n",
    "        if max == 0:\n",
    "            return 0\n",
    "        if cache[x][y][max] != -1:\n",
    "            return cache[x][y][max]\n",
    "        ans = 0\n",
    "        for d in self.dirs:\n",
    "            nx, ny = x + d[0], y + d[1]\n",
    "            ans += self.dfs(m, n, max - 1, nx, ny, cache)\n",
    "            ans %= self.MOD\n",
    "        cache[x][y][max] = ans\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        outCounts = 0\n",
    "        dp = [[[0] * n for _ in range(m)] for _ in range(maxMove + 1)]\n",
    "        dp[0][startRow][startColumn] = 1\n",
    "        for k in range(maxMove):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if dp[k][i][j] > 0: #可以不判断，但是会做很多无效的遍历； 1。count > 0表示当前位置可以到达，可以到达的上下左右移动才有意义；如果不判断的话，相当于不可到达的位置也进行上下左右移动，相邻位置计算路径时加的是0，这样是没有意义的\n",
    "                        for i1, j1 in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                            if 0 <= i1 < m and 0 <= j1 < n:\n",
    "                                dp[k + 1][i1][j1] = (dp[k + 1][i1][j1] + dp[k][i][j]) % MOD\n",
    "                            else:\n",
    "                                outCounts = (outCounts + dp[k][i][j]) % MOD\n",
    "        return outCounts\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        outCounts = 0\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[startRow][startColumn] = 1\n",
    "        for i in range(maxMove):\n",
    "            dpNew = [[0] * n for _ in range(m)]\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    if dp[j][k] > 0:\n",
    "                        for j1, k1 in [(j - 1, k), (j + 1, k), (j, k - 1), (j, k + 1)]:\n",
    "                            if 0 <= j1 < m and 0 <= k1 < n:\n",
    "                                dpNew[j1][k1] = (dpNew[j1][k1] + dp[j][k]) % MOD\n",
    "                            else:\n",
    "                                outCounts = (outCounts + dp[j][k]) % MOD\n",
    "            dp = dpNew\n",
    "        \n",
    "        return outCounts\n",
    "\n",
    "# 记忆化搜索\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.MOD = int(1e9+7)\n",
    "        self.dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "    def findPaths(self, m: int, n: int, max: int, r: int, c: int) -> int:\n",
    "        cache = [[[-1] * (max + 1) for _ in range(n)] for _ in range(m)]\n",
    "        return self.dfs(m, n, max, r, c, cache)\n",
    "    def dfs(self, m: int, n: int, max: int, x: int, y: int, cache: List[List[List[int]]]) -> int:\n",
    "        if x < 0 or x >= m or y < 0 or y >= n:\n",
    "            return 1\n",
    "        if max == 0:\n",
    "            return 0\n",
    "        if cache[x][y][max] != -1:\n",
    "            return cache[x][y][max]\n",
    "        ans = 0\n",
    "        for d in self.dirs:\n",
    "            nx, ny = x + d[0], y + d[1]\n",
    "            ans += self.dfs(m, n, max - 1, nx, ny, cache)\n",
    "            ans %= self.MOD\n",
    "        cache[x][y][max] = ans\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        outCounts = 0\n",
    "        dp = [[[0] * n for _ in range(m)] for _ in range(maxMove + 1)]\n",
    "        dp[0][startRow][startColumn] = 1\n",
    "        for i in range(maxMove):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    if dp[i][j][k] > 0:\n",
    "                        for j1, k1 in [(j - 1, k), (j + 1, k), (j, k - 1), (j, k + 1)]:\n",
    "                            if 0 <= j1 < m and 0 <= k1 < n:\n",
    "                                dp[i + 1][j1][k1] = (dp[i + 1][j1][k1] + dp[i][j][k]) % MOD\n",
    "                            else:\n",
    "                                outCounts = (outCounts + dp[i][j][k]) % MOD\n",
    "        \n",
    "        return outCounts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        dp=[[[0]*n for _ in range(m)] for _ in range(maxMove+1)]\n",
    "        dp[0][startRow][startColumn]=1\n",
    "        MOD=10**9+7\n",
    "        out_cnt=0\n",
    "        for k in range(1,maxMove+1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    for ni,nj in [(i,j+1),(i,j-1),(i-1,j),(i+1,j)]:\n",
    "                        if 0<=ni<m and 0<=nj<n:\n",
    "                            dp[k][ni][nj]=(dp[k][ni][nj]+dp[k-1][i][j])%MOD\n",
    "                        else:\n",
    "                            out_cnt=(out_cnt+dp[k-1][i][j])%MOD\n",
    "        return out_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        if maxMove==0:return 0\n",
    "        dp=[[[0]*n for _ in range(m)] for _ in range(maxMove)]\n",
    "        dp[0][startRow][startColumn]=1\n",
    "        for s in range(1,maxMove):\n",
    "            for r in range(m):\n",
    "                for c in range(n):\n",
    "                    uu=dp[s-1][r-1][c] if r>0 else 0\n",
    "                    dd=dp[s-1][r+1][c] if r<m-1 else 0\n",
    "                    ll=dp[s-1][r][c-1] if c>0 else 0\n",
    "                    rr=dp[s-1][r][c+1] if c<n-1 else 0\n",
    "                    dp[s][r][c]=uu+dd+ll+rr\n",
    "        return sum(z for x in dp for z in x[0]+x[-1]+[y[0] for y in x]+[y[-1] for y in x])%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mod = 1e9 + 7\n",
    "        self.dx = [-1, 1, 0, 0]\n",
    "        self.dy = [0, 0, -1, 1]\n",
    "\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        self.f = [[[-1 for _ in range(maxMove+1)] for _ in range(n)] for _ in range(m)]\n",
    "        return self.dp(m, n, maxMove, startRow, startColumn)\n",
    "\n",
    "    def dp(self, m, n, k, x, y):\n",
    "        if self.f[x][y][k] != -1:return self.f[x][y][k]\n",
    "        self.f[x][y][k] = 0\n",
    "        if k == 0:return self.f[x][y][k]\n",
    "        for i in range(4):\n",
    "            a = x + self.dx[i]\n",
    "            b = y + self.dy[i]\n",
    "            if a < 0 or a == m or b < 0 or b == n:\n",
    "                self.f[x][y][k] += 1\n",
    "            else:self.f[x][y][k] += self.dp(m, n, k-1, a, b)\n",
    "        self.f[x][y][k] %= self.mod\n",
    "        return int(self.f[x][y][k])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        modnum = 10**9+7\n",
    "        temp = m\n",
    "        m = n\n",
    "        n = temp\n",
    "        dp = [[[0 for _ in range(maxMove+1)] for _ in range(m+2)] for _ in range(n+2)]\n",
    "        dp[startRow+1][startColumn+1][0] = 1\n",
    "        for step in range(1, maxMove+1):\n",
    "            for i in range(0, n+2):\n",
    "                for j in range(0, m+2):\n",
    "                    if j >= 1 and j <= m and i > 1:\n",
    "                        dp[i][j][step] += dp[i-1][j][step-1]\n",
    "                    if j >= 1 and j <= m and i + 1 <= n:\n",
    "                        dp[i][j][step] += dp[i+1][j][step-1]\n",
    "                    if i >= 1 and i <= n and j > 1:\n",
    "                        dp[i][j][step] += dp[i][j-1][step-1]\n",
    "                    if i >= 1 and i <= n and j < m:\n",
    "                        dp[i][j][step] += dp[i][j+1][step-1]\n",
    "                    dp[i][j][step] %= modnum\n",
    "        ans = 0\n",
    "        for step in range(0, maxMove+1):\n",
    "            for i in range(1, n+1):\n",
    "                ans = (ans + dp[i][0][step] + dp[i][m+1][step]) % modnum\n",
    "            for j in range(1, m+1):\n",
    "                ans = (ans + dp[0][j][step] + dp[n+1][j][step]) % modnum\n",
    "        return ans\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        cache=[[[-1]*(maxMove+1) for _ in range(n) ] for _ in range(m)]\n",
    "        def dfs( move, i, j, m, n):\n",
    "            if i<0 or i>=m or j<0 or j>=n or move<0:\n",
    "                return 1 if move>=0 else 0\n",
    "\n",
    "            if move >=0 and move < min(i+1,j+1,m-i,n-j):\n",
    "                cache[i][j][move] = 0\n",
    "                return 0\n",
    "\n",
    "            if cache[i][j][move]!=-1:\n",
    "                return cache[i][j][move]\n",
    "\n",
    "            a1=dfs(move-1,i-1,j,m,n) %(10**9+7)\n",
    "            a2=dfs(move-1,i+1,j,m,n) %(10**9+7)\n",
    "            a3=dfs(move-1,i,j-1,m,n)%(10**9+7)\n",
    "            a4=dfs(move-1,i,j+1,m,n)%(10**9+7)\n",
    "            cache[i][j][move] = (a1+a2+a3+a4) %(10**9+7)\n",
    "            return cache[i][j][move]\n",
    "        \n",
    "        res = dfs( maxMove, startRow, startColumn, m,n)\n",
    "        return res\n",
    "\n",
    "        # def dfs(cache, move, i, j, m, n):\n",
    "        #     if i<0 or i>=m or j<0 or j>=n or move<0:\n",
    "        #         return 1 if move>=0 else 0\n",
    "\n",
    "        #     if move >=0 and move < min(i+1,j+1,m-i,n-j):\n",
    "        #         cache[i][j][move] = 0\n",
    "        #         return 0\n",
    "\n",
    "        #     if cache[i][j][move]!=-1:\n",
    "        #         return cache[i][j][move]\n",
    "\n",
    "        #     a1=dfs(cache,move-1,i-1,j,m,n) %(10**9+7)\n",
    "        #     a2=dfs(cache,move-1,i+1,j,m,n) %(10**9+7)\n",
    "        #     a3=dfs(cache,move-1,i,j-1,m,n)%(10**9+7)\n",
    "        #     a4=dfs(cache,move-1,i,j+1,m,n)%(10**9+7)\n",
    "        #     cache[i][j][move] = (a1+a2+a3+a4) %(10**9+7)\n",
    "        #     return cache[i][j][move]\n",
    "        \n",
    "        # res = dfs(cache, maxMove, startRow, startColumn, m,n)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = []\n",
    "\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        self.memo = [[[-1] * (maxMove + 1) for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        def dp(maxMove: int, i: int, j: int) -> int:        \n",
    "            # base case: 找到一条出界路径\n",
    "            if i < 0 or j < 0 or i >= m or j >= n:\n",
    "                return 1\n",
    "\n",
    "            # 防止冗余计算\n",
    "            if self.memo[i][j][maxMove] != -1:\n",
    "                return self.memo[i][j][maxMove]\n",
    "\n",
    "            # 在有限的步数内无法出界\n",
    "            if maxMove == 0:\n",
    "                return 0\n",
    "\n",
    "            # 状态转移方程\n",
    "            res = 0\n",
    "            res += dp(maxMove - 1, i - 1, j)\n",
    "            res += dp(maxMove - 1, i, j - 1)\n",
    "            res += dp(maxMove - 1, i + 1, j)\n",
    "            res += dp(maxMove - 1, i, j + 1)\n",
    "            \n",
    "            self.memo[i][j][maxMove] = res % 1000000007\n",
    "            return self.memo[i][j][maxMove]\n",
    "\n",
    "        return dp(maxMove, startRow, startColumn)\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        def helper(r, c, max_move, memo):\n",
    "            if r < 0 or c < 0 or r >= m or c >= n:\n",
    "                return 1\n",
    "            if (r, c, max_move) in memo:\n",
    "                return memo[(r, c, max_move)]\n",
    "            if max_move == 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                ans += helper(r+x, c+y, max_move-1, memo)\n",
    "            memo[(r, c, max_move)] = ans\n",
    "            return memo[(r, c, max_move)]\n",
    "        return helper(startRow, startColumn, maxMove, {}) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m, n, N, i, j):\n",
    "        dp = [{} for _ in range(N + 1)]   # 移动步数的dp, 字典存的是,当前位置和对应的可移除count\n",
    "        dp[0][(i, j)] = 1\n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        ans = 0\n",
    "        for step in range(1, N + 1):\n",
    "            for r, c in dp[step - 1]:  # 这里注意理解下, 有不同的(r,c)key,对应不同的count\n",
    "                count = dp[step - 1][(r, c)]\n",
    "                for dr, dc in dirs:\n",
    "                    nr, nc = dr + r, dc + c\n",
    "                    if nr >= m or nc >= n or nr < 0 or nc < 0:\n",
    "                        ans += count\n",
    "                        ans %= (10 ** 9 + 7)\n",
    "                    elif (nr, nc) in dp[step]:\n",
    "                        dp[step][(nr, nc)] += count\n",
    "                    else:\n",
    "                        dp[step][(nr, nc)] = count\n",
    "        return ans\n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "\n",
    "        MOD = 1e9 + 7\n",
    "        def dfs(cur_r, cur_c, move_left, m, n, cache):\n",
    "\n",
    "            if (cur_r, cur_c, move_left) in cache:\n",
    "                return cache[(cur_r, cur_c, move_left)]\n",
    "            \n",
    "            if move_left < 0:\n",
    "                return 0\n",
    "\n",
    "            if cur_r < 0 or cur_r >= m or cur_c < 0 or cur_c >= n:\n",
    "                cache[(cur_r, cur_c, move_left)] = 1\n",
    "                return cache[(cur_r, cur_c, move_left)]\n",
    "\n",
    "            up = dfs(cur_r - 1, cur_c, move_left-1, m, n, cache)\n",
    "            down = dfs(cur_r + 1, cur_c, move_left-1, m, n, cache)\n",
    "            left = dfs(cur_r, cur_c - 1, move_left-1, m, n, cache)\n",
    "            right = dfs(cur_r, cur_c + 1, move_left-1, m, n, cache)\n",
    "            cache[(cur_r, cur_c, move_left)] = int((up + down + left + right) % MOD)\n",
    "\n",
    "            return cache[(cur_r, cur_c, move_left)]\n",
    "        \n",
    "        return dfs(startRow, startColumn, maxMove, m, n, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findPaths(self, m, n, N, i, j):\n",
    "        dp = [{} for _ in range(N + 1)]\n",
    "        dp[0][(i, j)] = 1\n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        ans = 0\n",
    "        for step in range(1, N + 1):\n",
    "            for r, c in dp[step - 1]:\n",
    "                count = dp[step - 1][(r, c)]\n",
    "                for dr, dc in dirs:\n",
    "                    nr, nc = dr + r, dc + c\n",
    "                    if nr >= m or nc >= n or nr < 0 or nc < 0:\n",
    "                        ans += count\n",
    "                        ans %= (10 ** 9 + 7)\n",
    "                    elif (nr, nc) in dp[step]:\n",
    "                        dp[step][(nr, nc)] += count\n",
    "                    else:\n",
    "                        dp[step][(nr, nc)] = count\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # dfs\n",
    "        ret = [[[-1 for _ in range(maxMove + 1)] for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j, move):\n",
    "\n",
    "            if i < 0 or i > m - 1 or j < 0 or j > n - 1:\n",
    "                return 1\n",
    "            if move == 0:\n",
    "                return 0\n",
    "            if ret[i][j][move] != -1:\n",
    "                return ret[i][j][move]\n",
    "            ans = dfs(i - 1, j, move - 1) + dfs(i + 1, j, move - 1) + dfs(i, j - 1, move - 1) + dfs(i, j + 1, move - 1)\n",
    "            ret[i][j][move] = ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(startRow, startColumn, maxMove) % int(1e9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # 定义：从 (i, j) 出发，最大移动次数为 maxMove，出界的路径数量为 dp(maxMove, i, j)\n",
    "        def dp(maxMove: int, i: int, j: int) -> int:\n",
    "            # base case，找到一条出界路径\n",
    "            if i < 0 or j < 0 or i >= m or j >= n:\n",
    "                return 1\n",
    "            \n",
    "            # 避免冗余计算\n",
    "            if memo[i][j][maxMove] != -1:\n",
    "                return memo[i][j][maxMove]\n",
    "            \n",
    "            # 无法在有限的步数内出界\n",
    "            if maxMove == 0:\n",
    "                return 0\n",
    "            \n",
    "            # 状态转移关系：\n",
    "            # 在 maxMove 步之内从 (i, j) 踢出界的路径数量等于\n",
    "            # 在 maxMove - 1 步之内从 (i, j) 的相邻位置踢出界的路径数量之和\n",
    "            res = 0\n",
    "            res += dp(maxMove - 1, i, j + 1)\n",
    "            res += dp(maxMove - 1, i + 1, j)\n",
    "            res += dp(maxMove - 1, i - 1, j)\n",
    "            res += dp(maxMove - 1, i, j - 1)\n",
    "\n",
    "            memo[i][j][maxMove] = res % 1000000007\n",
    "\n",
    "            return memo[i][j][maxMove]\n",
    "\n",
    "\n",
    "        memo = [[[-1 for _ in range(maxMove + 1)] for _ in range(n)] for _ in range(m)]\n",
    "        for plane in memo:\n",
    "            for row in plane:\n",
    "                for k in range(maxMove+1):\n",
    "                    row[k] = -1\n",
    "        \n",
    "        return dp(maxMove, startRow, startColumn)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        directs = {(1, 0), (-1, 0), (0, 1), (0, -1)}\n",
    "        mod = 10 ** 9 + 7\n",
    "        memo = [[[-1 for _ in range(maxMove + 1)] for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j, moveCount):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return 1\n",
    "            if moveCount == 0:\n",
    "                return 0\n",
    "            if memo[i][j][moveCount] != -1:\n",
    "                return memo[i][j][moveCount]\n",
    "\n",
    "            ans = 0\n",
    "            for direct in directs:\n",
    "                new_i = i + direct[0]\n",
    "                new_j = j + direct[1]\n",
    "                ans += dfs(new_i, new_j, moveCount - 1)\n",
    "                ans %= mod\n",
    "            memo[i][j][moveCount] = ans\n",
    "            return ans\n",
    "        return dfs(startRow, startColumn, maxMove) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        memo = [[[-1 for _ in range(maxMove + 1)] for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j, moveCount):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return 1\n",
    "            \n",
    "            if moveCount == 0:\n",
    "                return 0\n",
    "\n",
    "            if memo[i][j][moveCount] != -1:\n",
    "                return memo[i][j][moveCount]\n",
    "\n",
    "            ans = 0\n",
    "            for direction in directions:\n",
    "                new_i = i + direction[0]\n",
    "                new_j = j + direction[1]\n",
    "                ans += dfs(new_i, new_j, moveCount - 1)\n",
    "                ans %= mod\n",
    "\n",
    "            memo[i][j][moveCount] = ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(startRow, startColumn, maxMove)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        if maxMove < 1: return 0\n",
    "        f = [[[0] * (maxMove + 1) for _ in range(n)] for _ in range(m)]\n",
    "        st = [[[0] * (maxMove + 1) for _ in range(n)] for _ in range(m)]\n",
    "        f[startRow][startColumn][0] = 1\n",
    "        st[startRow][startColumn][0] = True\n",
    "        dq = deque()\n",
    "        dq.append((startRow, startColumn, 0))\n",
    "        vi = [-1, 0, 1, 0]\n",
    "        vj = [0, 1, 0, -1]\n",
    "        res = 0\n",
    "        while dq:\n",
    "            x, y, cur = dq.popleft()\n",
    "            if cur >= maxMove: continue\n",
    "            st[x][y][cur] = False\n",
    "            for d in range(4):\n",
    "                a, b = x + vi[d], y + vj[d]\n",
    "                if 0 <= a < m and 0 <= b < n: \n",
    "                    f[a][b][cur + 1] += f[x][y][cur]\n",
    "                    if not st[a][b][cur + 1]:\n",
    "                        dq.append((a, b, cur + 1))\n",
    "                        st[a][b][cur + 1] = True\n",
    "                else: \n",
    "                    res = (res + f[x][y][cur]) % mod\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [[[0] * (n + 2) for _ in range(m + 2)] for _ in range(maxMove + 1)]\n",
    "        if maxMove == 0:\n",
    "            return 0 \n",
    "        for k in range(maxMove + 1):\n",
    "            for x in range(m + 2):\n",
    "                for y in range(n + 2):\n",
    "                    if x == 0 or y == 0 or x == m + 1 or y == n + 1:\n",
    "                        dp[k][x][y] = 1\n",
    "                    elif k == 0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        dp[k][x][y] = (dp[k][x][y] + dp[k - 1][x - 1][y] + dp[k - 1][x][y - 1] + dp[k - 1][x + 1][y] + dp[k - 1][x][y + 1]) % mod\n",
    "        return dp[maxMove][startRow + 1][startColumn + 1]\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 1000000007\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def paths(n, m, N, i, j):\n",
    "            # N 步走出去\n",
    "            # 1. 确保 n <= m, 减少重复计算\n",
    "            if n>m: return paths(m, n, N, j, i)\n",
    "            # 2. 确保 i<n/2, j<m/2, 减少重复计算\n",
    "            if i>n//2:\n",
    "                return paths(n, m, N, n-1-i, j)\n",
    "            if j>m//2:\n",
    "                return paths(n, m, N, i, m-1-j)\n",
    "            res = 0\n",
    "            if N==1:\n",
    "                if i==0: res += 1\n",
    "                if i==n-1: res += 1\n",
    "                if j==0: res += 1\n",
    "                if j==m-1: res += 1\n",
    "                return res\n",
    "            # 如果上下左右直着走都不能走出去, 提前终止\n",
    "            if i+N<n and i-N>=0 and j+N<m and j-N>=0:\n",
    "                return 0\n",
    "            if i>0: res += paths(n, m, N-1, i-1, j)\n",
    "            if j>0: res += paths(n, m, N-1, i, j-1)\n",
    "            if i<n-1: res += paths(n, m, N-1, i+1, j)\n",
    "            if j<m-1: res += paths(n, m, N-1, i, j+1)\n",
    "            return res%mod\n",
    "        # N 步以内走出去\n",
    "        return sum(paths(m, n, ni, startRow, startColumn) for ni in range(1, maxMove+1))%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        directions = [[1,0], [-1,0], [0,1], [0,-1]]\n",
    "\n",
    "        # # 1.dfs\n",
    "        # cache = [[[-1]*(maxMove+1) for _ in range(n)] for _ in range(m)]\n",
    "        # def dfs(x,y,k):\n",
    "        #     if x<0 or x>=m or y<0 or y>=n:\n",
    "        #         # 超出边界\n",
    "        #         return 1\n",
    "        #     if k==0:\n",
    "        #         # 没走出来\n",
    "        #         return 0\n",
    "        #     if cache[x][y][k]!=-1:\n",
    "        #         # 已经访问过，直接叠加\n",
    "        #         return cache[x][y][k]\n",
    "        #     ans = 0\n",
    "        #     for dx,dy in directions:\n",
    "        #         # 四个方向行进，并计算(x,y)上的出圈路径数\n",
    "        #         nx,ny = x+dx, y+dy\n",
    "        #         ans += dfs(nx, ny, k-1)\n",
    "        #         ans %= 1000000007\n",
    "        #     cache[x][y][k] = ans\n",
    "        #     return ans\n",
    "        # return dfs(startRow, startColumn, maxMove)\n",
    "\n",
    "        # 2.dp\n",
    "        dp = [[0]*(maxMove+1) for _ in range(m*n)]\n",
    "        def add(x,y,dp):\n",
    "            for k in range(1,maxMove+1):\n",
    "                dp[getIndex(x, y)][k]+=1\n",
    "        def getIndex(x,y):\n",
    "            return x*n+y\n",
    "        def parseIdx(idx):\n",
    "            return (idx//n, idx%n)\n",
    "\n",
    "        # 初始化边缘格子的路径数量\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0: add(i, j, dp)\n",
    "                if j==0: add(i, j, dp)\n",
    "                if i==m-1: add(i, j, dp)\n",
    "                if j==n-1: add(i, j, dp)\n",
    "        print(dp)\n",
    "        # 从小到达枚举【可移动步数】\n",
    "        for k in range(1,maxMove+1):\n",
    "            # 枚举所有的【位置】\n",
    "            for idx in range(m*n):\n",
    "                x,y = parseIdx(idx)\n",
    "                for dx,dy in directions:\n",
    "                    nx,ny = x+dx, y+dy\n",
    "                    if nx<0 or nx>=m or ny<0 or ny>=n:\n",
    "                        # 出边界的不管了 因为边缘的路径已经统计的\n",
    "                        continue\n",
    "                    nidx = getIndex(nx, ny)\n",
    "                    dp[nidx][k] += dp[idx][k-1]\n",
    "                    dp[nidx][k]%=1000000007\n",
    "        return dp[getIndex(startRow, startColumn)][maxMove]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        @lru_cache(None)\n",
    "        def dfs(x,y,move):\n",
    "            if min(x+1, y+1, m-x, n-y) > move:\n",
    "                return 0\n",
    "            \n",
    "            ans = 0\n",
    "            for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if nx < 0 or nx >= m or ny<0 or ny>=n:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    ans += dfs(nx, ny, move-1)\n",
    "            return ans % MOD\n",
    "        \n",
    "        return dfs(startRow, startColumn, maxMove)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        cache = [[[-1] * (maxMove + 1) for _ in range(n)] for _ in range(m)]\n",
    "        print(cache)\n",
    "        def dfs(i: int, j: int, k: int) -> int:\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return 1\n",
    "            if k <= 0:\n",
    "                return 0\n",
    "            if cache[i][j][k] != -1:\n",
    "                return cache[i][j][k]\n",
    "            ans = dfs(i, j - 1, k - 1) + dfs(i, j + 1, k - 1) + dfs(i - 1, j, k - 1) + dfs(i + 1, j, k - 1)\n",
    "            ans %= mod\n",
    "            cache[i][j][k] = ans\n",
    "            return ans\n",
    "        return dfs(startRow, startColumn, maxMove)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mem = [{} for _ in range(maxMove + 1)]\n",
    "        def dfs(num, i, j):\n",
    "            if (i, j) in mem[num]:\n",
    "                return mem[num][(i, j)]\n",
    "            if (i < 0 or i >= m or j < 0 or j >= n):\n",
    "                return 1\n",
    "            if num == 0: return 0\n",
    "            if i - num >= 0 and j - num >= 0 and i + num < m and j + num < n: return 0\n",
    "            r = 0\n",
    "            r += dfs(num - 1, i - 1, j) % (10 ** 9 + 7)\n",
    "            r += dfs(num - 1, i + 1, j) % (10 ** 9 + 7)\n",
    "            r += dfs(num - 1, i, j - 1) % (10 ** 9 + 7)\n",
    "            r += dfs(num - 1, i, j + 1) % (10 ** 9 + 7)\n",
    "            mem[num][(i, j)] = r % (10 ** 9 + 7)\n",
    "            return r % (10 ** 9 + 7)\n",
    "        res = dfs(maxMove, startRow, startColumn)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # maxmove, m, n\n",
    "        dp = [[[0] * n for _ in range(m)] for _ in range(maxMove+1)]\n",
    "\n",
    "        for move in range(1, maxMove+1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i == 0:\n",
    "                        dp[move][i][j] += 1\n",
    "                    if j == 0:\n",
    "                        dp[move][i][j] += 1\n",
    "                    if i == m-1:\n",
    "                        dp[move][i][j] += 1\n",
    "                    if j == n-1:\n",
    "                        dp[move][i][j] += 1\n",
    "\n",
    "        for move in range(2, maxMove+1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    for ni, nj in [(i+1, j), (i, j+1), (i-1, j), (i, j-1)]:\n",
    "                        if 0 <= ni < m and 0 <= nj < n:\n",
    "                            # taking modulo before totaling up the sum is very important\n",
    "                            dp[move][i][j] += dp[move-1][ni][nj] % (1e9 + 7)\n",
    "\n",
    "        return int(dp[maxMove][startRow][startColumn] % (1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "#         mod = 10 ** 9 + 7\n",
    "#         directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "#         # 记录已经计算过的路径数量\n",
    "#         memo = [[[-1 for _ in range(maxMove + 1)] for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "#         def dfs(i, j, movecount):\n",
    "#             if i < 0 or i >= m or j < 0 or j >= n:\n",
    "#                 return 1\n",
    "            \n",
    "#             if movecount == 0:\n",
    "#                 return 0\n",
    "            \n",
    "#             if memo[i][j][movecount] != -1:\n",
    "#                 return memo[i][j][movecount]\n",
    "\n",
    "#             ans = 0\n",
    "#             for direction in directions:\n",
    "#                 new_i = i + direction[0]\n",
    "#                 new_j = j + direction[1]\n",
    "#                 ans += dfs(new_i, new_j, movecount-1)\n",
    "#                 ans %= mod\n",
    "\n",
    "#             memo[i][j][movecount] = ans\n",
    "#             return ans\n",
    "\n",
    "#         return dfs(startRow, startColumn, maxMove)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "        dp = [[[0 for _ in range(maxMove + 1)] for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for k in range(1, maxMove + 1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    for direction in directions:\n",
    "                        new_i = i + direction[0]\n",
    "                        new_j = j + direction[1]\n",
    "                        if 0 <= new_i < m and 0 <= new_j < n:\n",
    "                            dp[i][j][k] = (dp[i][j][k] + dp[new_i][new_j][k - 1]) % mod \n",
    "                        else:\n",
    "                            dp[i][j][k] = (dp[i][j][k] + 1) % mod\n",
    "        \n",
    "        return dp[startRow][startColumn][maxMove]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        dp = [[[0]*n for _ in range(m)] for _ in range(maxMove+1)]\n",
    "\n",
    "        # for i in range(m):\n",
    "        #     dp[1][i][0],dp[1][i][-1] =1,1\n",
    "        # for j in range(n):\n",
    "        #     dp[1][0][j],dp[1][-1][j] =1,1\n",
    "        # dp[1][0][0],dp[1][0][n-1],dp[1][m-1][0],dp[1][m-1][n-1]=2,2,2,2\n",
    "        for move in range(1,maxMove+1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i-1>=0:\n",
    "                        dp[move][i][j]+=dp[move-1][i-1][j]\n",
    "                    else:dp[move][i][j]+=1\n",
    "\n",
    "                    if i+1<m:\n",
    "                        dp[move][i][j]+=dp[move-1][i+1][j]\n",
    "                    else:\n",
    "                        dp[move][i][j]+=1\n",
    "                    if j-1>=0:\n",
    "                        dp[move][i][j]+=dp[move-1][i][j-1]\n",
    "                    else: dp[move][i][j]+=1\n",
    "                    if j+1<n:\n",
    "                        dp[move][i][j]+=dp[move-1][i][j+1]\n",
    "                    else:  dp[move][i][j]+=1\n",
    "                    # dp[move][i][j] +=dp[move-1][i][j]\n",
    "                    dp[move][i][j] = dp[move][i][j]%(10**9+7)\n",
    "            # print(move , dp[move])\n",
    "        return dp[maxMove][startRow][startColumn]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def findPaths(self, n: int, m: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        if maxMove == 0: \n",
    "            return 0\n",
    "        f = [[[0] * (maxMove + 1) for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][0][1] += 1\n",
    "            f[i][m - 1][1] += 1\n",
    "        for j in range(m):\n",
    "            f[0][j][1] += 1\n",
    "            f[n - 1][j][1] += 1\n",
    "        dx = [-1, 0, 1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for k in range(1, maxMove + 1):\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                \n",
    "                    for u in range(4):\n",
    "                        a = i + dx[u]\n",
    "                        b = j + dy[u]\n",
    "                        if 0 <= a < n and 0 <= b < m:\n",
    "                            f[i][j][k] += f[a][b][k - 1]\n",
    "                            f[i][j][k] %= MOD\n",
    "        res = 0\n",
    "        for k in range(1, maxMove + 1):\n",
    "            res += f[startRow][startColumn][k]\n",
    "            res %= MOD\n",
    "        return res % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        dp = [[ [0] * (n+2) for _ in range(m + 2)] for _ in range(maxMove + 1)]\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        if maxMove == 0:\n",
    "            return 0\n",
    "        \n",
    "        for k in range(maxMove + 1):\n",
    "            for i in range(m + 2):\n",
    "                for j in range (n + 2):\n",
    "                   if i == 0 or j == 0 or i == m + 1 or j == n + 1:\n",
    "                        dp[k][i][j] = 1\n",
    "\n",
    "        for k in range(1, maxMove + 1):\n",
    "            for i in range(1, m + 1):\n",
    "                for j in range (1, n + 1):\n",
    "                        dp[k][i][j] += (dp[k-1][i-1][j] + dp[k-1][i][j-1] + dp[k-1][i][j+1] + dp[k-1][i+1][j]) % mod\n",
    "\n",
    "        return dp[maxMove][startRow+1][startColumn+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        table = {}\n",
    "        def find_next(i,px,py):\n",
    "            if i <= maxMove:\n",
    "                if not 0 <= px <= m-1 or not 0 <= py <= n-1:\n",
    "                    return 1\n",
    "            if i > maxMove:\n",
    "                return 0\n",
    "\n",
    "            if (i,px,py) in table:\n",
    "                return table[(i,px,py)]\n",
    "            ans = find_next(i+1,px-1,py) + find_next(i+1,px+1,py) + find_next(i+1,px,py-1) + find_next(i+1,px,py+1)\n",
    "            table[(i,px,py)] = ans\n",
    "            return ans\n",
    "        return find_next(0,startRow,startColumn) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # cnt 与 (i, j), start 奇偶性相关\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i, j, cnt):\n",
    "            if cnt >= maxMove:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            # 取决于周围格子数量\n",
    "            if i in (0, m-1) or j in (0, n-1):\n",
    "                t = 4\n",
    "                for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        t -= 1\n",
    "                ans += t\n",
    "            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):\n",
    "                \n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    ans += dfs(x, y, cnt+1)\n",
    "            return ans\n",
    "        return dfs(startRow, startColumn, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def rec(x, y, l):\n",
    "            nonlocal m\n",
    "            nonlocal n \n",
    "            if l == 0:\n",
    "                return 0\n",
    "            a = 1 if x == 0 else rec(x - 1, y, l - 1)\n",
    "            b = 1 if y == 0 else rec(x, y - 1, l - 1)\n",
    "            c = 1 if x == m - 1 else rec(x + 1, y, l - 1)\n",
    "            d = 1 if y == n - 1 else rec(x, y + 1, l - 1)\n",
    "            return a + b + c + d \n",
    "        \n",
    "        return rec(startRow, startColumn, maxMove) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD  = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, left):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return 1\n",
    "            if left <= 0:\n",
    "                return 0\n",
    "            if min(i + 1, j + 1, m - i, n - j) > left:\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            dx = [1, -1, 0, 0]\n",
    "            dy = [0, 0, 1, -1]\n",
    "            for k in range(4):\n",
    "                x = i + dx[k]\n",
    "                y = j + dy[k]\n",
    "                res = (res + dfs(x, y, left - 1)) % MOD\n",
    "            return res\n",
    "        return dfs(startRow, startColumn, maxMove) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        \n",
    "        \n",
    "        mod=10**9+7\n",
    "        @cache\n",
    "        def dfs(i,j,leftmove):\n",
    "            #出界判断\n",
    "            if not(0<=i<m) or not(0<=j<n):\n",
    "                return 1\n",
    "            #剪枝\n",
    "            if leftmove<min(m-i,i+1) and leftmove<min(n-j,j+1):\n",
    "                return 0\n",
    "            return dfs(i+1,j,leftmove-1)+dfs(i-1,j,leftmove-1)+dfs(i,j-1,leftmove-1)+dfs(i,j+1,leftmove-1)\n",
    "        return dfs(startRow,startColumn,maxMove)%mod\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def func(i, j, c):\n",
    "            if 0 <= i < m and 0 <= j < n:\n",
    "                if c < min(i+1, m-i, j+1, n-j):\n",
    "                    res = 0 \n",
    "                else:\n",
    "                    res = func(i-1, j, c-1) + func(i+1, j, c-1) + func(i, j-1, c-1) + func(i, j+1, c-1)\n",
    "            else:\n",
    "                res = 1\n",
    "            return res % (10**9 + 7)\n",
    "        res = func(startRow, startColumn, maxMove)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dx = [ -1, 0, 1, 0 ]\n",
    "        dy = [ 0, 1, 0, -1 ]\n",
    "        dp = [ [ [0] * n for _ in range(m) ] for _ in range(maxMove+1) ]\n",
    "        for mv in range(1, maxMove+1):\n",
    "            for x in range(m):\n",
    "                for y in range(n):\n",
    "                    for d in range(4):\n",
    "                        nx, ny = x + dx[d], y + dy[d]\n",
    "                        if 0 <= nx < m and 0 <= ny < n:\n",
    "                            dp[mv][x][y] += (dp[mv-1][nx][ny]) % mod\n",
    "                        else:\n",
    "                            dp[mv][x][y] += 1\n",
    "        # print(dp)\n",
    "        return dp[-1][startRow][startColumn] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # m*n矩阵，每个元素是 长度50的数组，表示在该单元格，移动x次出界的路径数量。\n",
    "        if maxMove==0:\n",
    "            return 0\n",
    "\n",
    "        MOD = 10**9+7\n",
    "        dp = [[[0]*maxMove for _ in range(n)] for _ in range(m)]\n",
    "        # move = 1\n",
    "        for i in range(n): \n",
    "            dp[0][i][0] += 1\n",
    "            dp[-1][i][0] += 1\n",
    "        for i in range(m): \n",
    "            dp[i][0][0] += 1\n",
    "            dp[i][-1][0] += 1\n",
    "\n",
    "        dr = [1,-1,0,0]\n",
    "        dc = [0,0,1,-1]\n",
    "        for k in range(1,maxMove):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    for d in range(4):\n",
    "                        cr,cc = i+dr[d],j+dc[d]\n",
    "                        if cr>=0 and cr<m and cc>=0 and cc<n:\n",
    "                            dp[i][j][k] += dp[cr][cc][k-1]\n",
    "                        else:\n",
    "                            dp[i][j][k] \n",
    "                    pass\n",
    "    \n",
    "        return sum(dp[startRow][startColumn])%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:\n",
    "        '''\n",
    "        移除边界的前一步到达边界，边界总数是2*(m+n-2),一个思路是分别计算达到这些位置\n",
    "        dp[i][j][k] 代表到达i,j位置，mov次数为k的路径数量\n",
    "        dp[i][j][k] = dp[i-1][j][k-1] + dp[i][j-1][k-1] + dp[i+1][j][k-1]\n",
    "        '''\n",
    "        dp = [[[0] * (n + 2) for _ in range(m + 2)] for _ in range(N + 1)]\n",
    "        \n",
    "        for r in range(m + 2):\n",
    "            dp[0][r][0] = 1\n",
    "            dp[0][r][n + 1] = 1\n",
    "\n",
    "        for c in range(n + 2):\n",
    "            dp[0][0][c] = 1\n",
    "            dp[0][m + 1][c] = 1\n",
    "\n",
    "        for k in range(1, N + 1):\n",
    "            for r in range(1, m + 1):\n",
    "                for c in range(1, n + 1):\n",
    "                    dp[k][r][c] = dp[k - 1][r - 1][c] + dp[k - 1][r + 1][c] + dp[k - 1][r][c - 1] + dp[k - 1][r][c + 1]\n",
    "        res = 0\n",
    "        for k in range(1, N + 1):\n",
    "            res += dp[k][i + 1][j + 1]\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(x, y, k):\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                return 1\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for diffX, diffY in [[1, 0], [-1, 0], [0, -1], [0, 1]]:\n",
    "                nx, ny = diffX + x, diffY + y\n",
    "                ans += dfs(nx, ny, k-1)\n",
    "                ans %= mod\n",
    "            return ans\n",
    "        return dfs(startRow, startColumn, maxMove)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, k):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return 1\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            return dfs(i - 1, j , k - 1) + dfs(i + 1, j ,k - 1) + dfs(i, j - 1, k - 1) + dfs(i, j + 1, k - 1)\n",
    "\n",
    "        return dfs(startRow, startColumn, maxMove) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def func(i, j, c):\n",
    "            if 0 <= i < m and 0 <= j < n:\n",
    "                if c == 0:#c < min(i+1, n-i, j+1, n-j):\n",
    "                    res = 0 \n",
    "                else:\n",
    "                    res = func(i-1, j, c-1) + func(i+1, j, c-1) + func(i, j-1, c-1) + func(i, j+1, c-1)\n",
    "            else:\n",
    "                res = 1\n",
    "            return res % (10**9 + 7)\n",
    "        res = func(startRow, startColumn, maxMove)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 1000000007\n",
    "        dx = [0,0,1,-1]\n",
    "        dy = [-1,1,0,0]\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y, step):\n",
    "            if x >= m or y >= n or x < 0 or y < 0:\n",
    "                return 1\n",
    "            if step == 0:\n",
    "                return 0\n",
    "            cnt = 0\n",
    "            for i in range(4):\n",
    "                nx, ny = x + dx[i], y + dy[i]\n",
    "                cnt = (cnt + dfs(nx, ny, step - 1)) % mod\n",
    "            return cnt\n",
    "        return dfs(startRow, startColumn, maxMove)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "\n",
    "        mod=10**9+7\n",
    "\n",
    "        @cache\n",
    "\n",
    "        def search(r,c,move):\n",
    "            if r==-1 or c==-1 or c==n or r==m:\n",
    "                return 1\n",
    "            else:\n",
    "                if move==0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return search(r,c-1,move-1)+search(r,c+1,move-1)+search(r-1,c,move-1)+search(r+1,c,move-1)\n",
    "\n",
    "\n",
    "        return search(startRow,startColumn,maxMove)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        @cache\n",
    "        def func(i, j, x):\n",
    "            if 0 <= i < m and 0 <= j < n:\n",
    "                if x == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return func(i+1, j, x-1) + func(i-1, j, x-1) + func(i, j+1, x-1) + func(i, j-1, x-1)\n",
    "            if x >= 0:\n",
    "                return 1\n",
    "            return 0\n",
    "\n",
    "        return func(startRow, startColumn, maxMove) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @lru_cache(None)\n",
    "        def subpath(r,c,move):\n",
    "            # [r,c]此刻的位置，move能移动的次数\n",
    "            if r == -1 or r == m or c == -1 or c == n:\n",
    "                # 此时球已经出界\n",
    "                return 1\n",
    "            else: # 球没有出界\n",
    "                if move == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    # 想想一棵树，到叶子节点，需要做什么？\n",
    "                    return subpath(r, c+1, move - 1) + subpath(r-1,c,move-1) + subpath(r+1, c, move - 1) + subpath(r, c-1, move - 1)\n",
    "        return subpath(startRow,startColumn,maxMove) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        @cache\n",
    "        def func(row, col, rest_move):\n",
    "            if (not 0 <= row < m or not 0 <= col < n) and rest_move >= 0:\n",
    "                return 1\n",
    "            if rest_move <= 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                res += func(row + x, col + y, rest_move - 1)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return func(startRow, startColumn, maxMove) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        @cache\n",
    "        def dfs(m, n, maxMove, x, y):\n",
    "            if x >=m or y >= n or x <0 or y <0:\n",
    "                return 1\n",
    "            \n",
    "            if maxMove == 0:\n",
    "                return 0\n",
    "            sum_ = 0\n",
    "            for i, j in direct:\n",
    "                sum_ = (sum_ + dfs(m, n, maxMove-1, x+i, y+j)) % (10 ** 9 + 7)\n",
    "            return sum_\n",
    "        \n",
    "        return dfs(m, n, maxMove, startRow, startColumn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def recur(x,y,k,m,n):\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return 1\n",
    "            elif k == 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for nx,ny in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                res += recur(x+nx,y+ny,k-1,m,n)\n",
    "            return res%(10**9+7)\n",
    "        return recur(startRow,startColumn,maxMove,m,n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        @cache\n",
    "        def dfs(m, n, maxMove, x, y):\n",
    "            if x >=m or y >= n or x <0 or y <0:\n",
    "                return 1\n",
    "            \n",
    "            if maxMove == 0:\n",
    "                return 0\n",
    "            sum_ = 0\n",
    "            for i, j in direct:\n",
    "                sum_ = sum_ + dfs(m, n, maxMove-1, x+i, y+j)\n",
    "            return sum_\n",
    "        \n",
    "        return dfs(m, n, maxMove, startRow, startColumn) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:\n",
    "        if i < 0 or i >= m or j < 0 or j >= n:\n",
    "            return 1\n",
    "        if not N:\n",
    "            return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = 0\n",
    "        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "            cnt += self.findPaths(m, n, N - 1, i + dx, j + dy)\n",
    "        return cnt % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        @cache\n",
    "        def dfs(node, cnt):\n",
    "            x, y = node\n",
    "            if not (0 <= x < m and 0 <= y < n):\n",
    "                return 1\n",
    "            if cnt == 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for nx, ny in (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1):\n",
    "                res += dfs((nx, ny), cnt - 1)\n",
    "            return res \n",
    "        return dfs((startRow, startColumn), maxMove) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # 假设用记忆化搜索，m*n表示范围,sr,sc是起点\n",
    "        # 同时需要注意它的出界定义，只能在最后一步出界\n",
    "        # 之后转dp\n",
    "\n",
    "        memo = dict()\n",
    "        mod = 10**9 + 7\n",
    "        # 状态转移为 dfs(i,j,k) = dfs(...,...,k-1),# 四个方向\n",
    "        # 基态为，初始化如下\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                invalid = 0\n",
    "                if i == 0:\n",
    "                    invalid += 1\n",
    "                if i == m-1:\n",
    "                    invalid += 1\n",
    "                if j == 0:\n",
    "                    invalid += 1\n",
    "                if j == n-1:\n",
    "                    invalid += 1\n",
    "                memo[(i,j,1)] = invalid\n",
    "\n",
    "        direc = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def dfs(i,j,k): # 当前坐标点走k步的结果\n",
    "            if (i,j,k) in memo:\n",
    "                return memo[(i,j,k)]\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            \n",
    "            temp = 0\n",
    "            for di in direc:\n",
    "                new_i = i + di[0]\n",
    "                new_j = j + di[1]\n",
    "                if 0<=new_i<m and 0<=new_j<n:\n",
    "                    temp += dfs(new_i,new_j,k-1)\n",
    "            temp %= mod\n",
    "            memo[(i,j,k)] = temp\n",
    "            return temp \n",
    "\n",
    "        for t in range(1,maxMove+1):\n",
    "            dfs(startRow,startColumn,t)\n",
    "        # print(memo)\n",
    "        ans = 0\n",
    "        for t in range(1,maxMove+1):\n",
    "            ans += memo.get((startRow,startColumn,t),0)\n",
    "        return ans%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(node, cnt):\n",
    "            x, y = node\n",
    "            if not (0 <= x < m and 0 <= y < n):\n",
    "                return 1\n",
    "            if cnt == 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for nx, ny in (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1):\n",
    "                res += dfs((nx, ny), cnt - 1)\n",
    "            return res \n",
    "        return dfs((startRow, startColumn), maxMove) % (10 ** 9 + 7)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        @cache\n",
    "        def dfs(node, cnt):\n",
    "            x, y = node\n",
    "            if not (0 <= x < m and 0 <= y < n):\n",
    "                return 1\n",
    "            if cnt == 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for nx, ny in (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1):\n",
    "                res += dfs((nx, ny), cnt - 1)\n",
    "            return res \n",
    "        return dfs((startRow, startColumn), maxMove) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(m,n,x,y,step,maxMove):\n",
    "            \n",
    "            if step > maxMove:\n",
    "                return 0\n",
    "            if x < 0 or x >= m or y < 0 or y >= n :\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for nx,ny in ((1,0),(-1,0),(0,1),(0,-1)):\n",
    "                dx = x + nx\n",
    "                dy = y + ny\n",
    "                ans += dfs(m,n,dx,dy,step+1,maxMove)\n",
    "            return ans % self.mod\n",
    "        self.mod = 10 ** 9 + 7\n",
    "        return dfs(m,n,startRow,startColumn,0,maxMove)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # 暴力递归\n",
    "        @cache\n",
    "        def recrusive(m,n,max_move,row,col):\n",
    "            if max_move < 0:\n",
    "                return 0\n",
    "            if max_move >= 0 and (row < 0 or row > m-1 or col < 0 or col > n-1):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            ans += recrusive(m,n,max_move-1,row-1,col) # 往上\n",
    "            ans += recrusive(m,n,max_move-1,row+1,col) # 往下\n",
    "            ans += recrusive(m,n,max_move-1,row,col-1) # 往左\n",
    "            ans += recrusive(m,n,max_move-1,row,col+1) # 往右\n",
    "            return ans % (1e9+7)\n",
    "\n",
    "        return recrusive(m,n,maxMove,startRow,startColumn)\n",
    "\n",
    "        # 记忆化搜索，某一个位置可以从它的上下左右到达它，所以可以用一个dp数组保存当前位置\n",
    "        # 剩余x步时，将球移除边界的路径数量\n",
    "        # dp = [[[-1]*(maxMove+1) for _ in range(n)] for _ in range(m)]  # dp[i][j][k]表示小球在位置[i,j]，剩余移动次数为k时，将球移出边界的路径数量\n",
    "        # def recrusive(m,n,max_move,row,col):\n",
    "        #     nonlocal dp\n",
    "        #     if max_move < 0:\n",
    "        #         return 0\n",
    "        #     if max_move >= 0 and (row < 0 or row > m-1 or col < 0 or col > n-1):\n",
    "        #         return 1\n",
    "        #     if dp[row][col][max_move] != -1:\n",
    "        #         return dp[row][col][max_move]\n",
    "        #     ans = 0\n",
    "        #     ans += recrusive(m,n,max_move-1,row-1,col) # 往上\n",
    "        #     ans += recrusive(m,n,max_move-1,row+1,col) # 往下\n",
    "        #     ans += recrusive(m,n,max_move-1,row,col-1) # 往左\n",
    "        #     ans += recrusive(m,n,max_move-1,row,col+1) # 往右\n",
    "        #     dp[row][col][max_move] = ans\n",
    "        #     return dp[row][col][max_move]\n",
    "\n",
    "        # return recrusive(m,n,maxMove,startRow,startColumn) % (1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        directions = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        dp = [[[0] * (maxMove + 1) for _ in range(n)] for _ in range(m)]    # 代表从位置 i,j 出发，可用步数不超过k时的路径数量dp[i][j][k]\n",
    "\n",
    "        for k in range(1, maxMove+1):\n",
    "            for i in range(0, m):\n",
    "                for j in range(0, n):\n",
    "                    if i == 0:\n",
    "                        dp[i][j][k] += 1\n",
    "                    if j == 0:\n",
    "                        dp[i][j][k] += 1\n",
    "                    if i == m-1:\n",
    "                        dp[i][j][k] += 1\n",
    "                    if j == n-1:\n",
    "                        dp[i][j][k] += 1\n",
    "        \n",
    "        for k in range(1, maxMove+1):\n",
    "            for i in range(0, m):\n",
    "                for j in range(0, n):\n",
    "                    \n",
    "                    for dir in directions:\n",
    "                        i_row, j_line = dir\n",
    "                        \n",
    "                        if 0 <= i+i_row < m and 0 <= j+j_line < n:\n",
    "                            dp[i][j][k] += dp[i+i_row][j+j_line][k-1]\n",
    "                            dp[i][j][k] %= MOD\n",
    "\n",
    "        print(dp)\n",
    "        return dp[startRow][startColumn][maxMove]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        dfs_dic = {}\n",
    "        @lru_cache(None)\n",
    "        def dfs(x=startRow, y=startColumn, move=0):\n",
    "            if (x, y, move) in dfs_dic:return dfs_dic[(x, y, move)]\n",
    "            ans = 0\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                ans = 1\n",
    "            elif move < maxMove:\n",
    "                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                    ans += dfs(x+dx, y+dy, move+1)\n",
    "            dfs_dic[(x, y, move)] = ans\n",
    "            return ans\n",
    "        return dfs()%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        def dp(row, column, move):\n",
    "            key = (row, column, move)\n",
    "            if key in d:\n",
    "                return d[key]\n",
    "            if move == 1:\n",
    "                if row == 0:\n",
    "                    d[key] += 1\n",
    "                if row == m - 1:\n",
    "                    d[key] += 1\n",
    "                if column == 0:\n",
    "                    d[key] += 1\n",
    "                if column == n - 1:\n",
    "                    d[key] += 1\n",
    "                return d[key]\n",
    "            for new_row, new_column in [(row - 1, column), (row + 1,  column), (row, column - 1), (row, column + 1)]:\n",
    "                if new_row >= 0 and new_row < m and new_column >= 0 and new_column < n:\n",
    "                    d[(new_row, new_column, move - 1)] = dp(new_row, new_column, move - 1)\n",
    "                    d[key] += d[(new_row, new_column, move - 1)]\n",
    "            return d[key]\n",
    "            \n",
    "            \n",
    "        d = defaultdict(int)\n",
    "        res = 0\n",
    "        for move in range(1, maxMove + 1):\n",
    "            res += dp(startRow, startColumn, move)\n",
    "            \n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        return self.dfs(m, n, maxMove, startRow, startColumn)\n",
    "    \n",
    "    @functools.lru_cache(None)\n",
    "    def dfs(self, m, n, steps, row, column):\n",
    "        if min(row + 1, m - row, column + 1, n - column) > steps or steps == 0:\n",
    "            return 0\n",
    "        sumPath = 0\n",
    "        sumPath += (1 if row == 0 else self.dfs(m, n, steps -1, row-1, column))\n",
    "        sumPath += (1 if row == m-1 else self.dfs(m, n, steps -1, row+1, column))\n",
    "        sumPath += (1 if column == 0 else self.dfs(m, n, steps -1, row, column-1))\n",
    "        sumPath += (1 if column == n-1 else self.dfs(m, n, steps -1, row, column+1))\n",
    "        return sumPath % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        m1, n1, t = m - 1, n - 1, 10**9 + 7\n",
    "        \n",
    "        def g(i, j):\n",
    "            if i:\n",
    "                yield i - 1, j\n",
    "            if i < m1:\n",
    "                yield i + 1, j\n",
    "            if j:\n",
    "                yield i, j - 1\n",
    "            if j < n1:\n",
    "                yield i, j + 1\n",
    "        \n",
    "        @cache\n",
    "        def f(i, j, x):\n",
    "            if x == 1:\n",
    "                return (i == 0) + (i == m1) + (j == 0) + (j == n1)\n",
    "            x -= 1\n",
    "            return sum(f(i1, j1, x) for i1, j1 in g(i, j)) % t\n",
    "            \n",
    "        return sum(f(startRow, startColumn, i) for i in range(1, maxMove + 1)) % t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        @cache\n",
    "        def recur(i, j, mv):\n",
    "            if mv == 1:\n",
    "                return (i == 0) + (i == m - 1) + (j == 0) + (j == n - 1)\n",
    "            cnt = 0\n",
    "            if i:\n",
    "                cnt += recur(i - 1, j, mv - 1)\n",
    "            if j:\n",
    "                cnt += recur(i, j - 1, mv - 1)\n",
    "            if i < m - 1:\n",
    "                cnt += recur(i + 1, j, mv - 1)\n",
    "            if j < n - 1:\n",
    "                cnt += recur(i, j + 1, mv - 1)\n",
    "            return cnt % MOD\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, maxMove + 1):\n",
    "            res += recur(startRow, startColumn, i)\n",
    "\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    dirc = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "    @lru_cache(None)\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # 出界了\n",
    "        if startRow < 0 or startRow == m or startColumn < 0 or startColumn == n:\n",
    "            return 1\n",
    "        # 没移动次数了或者怎么移动也不可能出界了\n",
    "        if not maxMove or (m - maxMove > startRow > maxMove - 1 and n - maxMove > startColumn > maxMove - 1):\n",
    "            return 0\n",
    "        # 向四个方向移动的结果的和\n",
    "        ans = 0\n",
    "        for dx, dy in self.dirc:\n",
    "            ans = (ans + self.findPaths(m, n, maxMove - 1, startRow + dx, startColumn + dy)) % self.mod\n",
    "        return ans\n",
    "        \n",
    "\n",
    "    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        direction=[(0,1),(0,-1),(1,0),(-1,0)]       \n",
    "        if startRow<0 or startRow==m or startColumn<0 or startColumn==n:\n",
    "            return 1\n",
    "        if maxMove==0:\n",
    "            return 0\n",
    "        if not maxMove or m-maxMove>startRow>maxMove+1 and n-maxMove>startColumn>maxMove-1:\n",
    "            return 0\n",
    "        ans=0\n",
    "        for dx,dy in direction:\n",
    "            ans=(ans+self.findPaths(m,n,maxMove-1,startRow+dx,startColumn+dy))%(10**9+7)\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    dirc = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        if startRow < 0 or startRow == m or startColumn < 0 or startColumn == n:\n",
    "            return 1\n",
    "        if not maxMove or (m - maxMove > startRow > maxMove - 1 and n - maxMove > startColumn > maxMove - 1):\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for dx, dy in self.dirc:\n",
    "            ans = (ans + self.findPaths(m, n, maxMove - 1, startRow + dx, startColumn + dy)) % self.mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "    # def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # MOD = 10**9 + 7\n",
    "        # outCounts = 0\n",
    "        # dp = [[0] * n for _ in range(m)]\n",
    "        # dp[startRow][startColumn] = 1\n",
    "        # for i in range(maxMove):\n",
    "        #     dpNew = [[0] * n for _ in range(m)]\n",
    "        #     for j in range(m):\n",
    "        #         for k in range(n):\n",
    "        #             if dp[j][k] > 0:\n",
    "        #                 for j1, k1 in [(j - 1, k), (j + 1, k), (j, k - 1), (j, k + 1)]:\n",
    "        #                     if 0 <= j1 < m and 0 <= k1 < n:\n",
    "        #                         dpNew[j1][k1] = (dpNew[j1][k1] + dp[j][k]) % MOD\n",
    "        #                     else:\n",
    "        #                         outCounts = (outCounts + dp[j][k]) % MOD\n",
    "        #     dp = dpNew\n",
    "        \n",
    "        # return outCounts\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    dirc = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "    @lru_cache(None)\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        # 出界了\n",
    "        if startRow < 0 or startRow == m or startColumn < 0 or startColumn == n:\n",
    "            return 1\n",
    "        # 没移动次数了或者怎么移动也不可能出界了\n",
    "        if not maxMove or (m - maxMove > startRow > maxMove - 1 and n - maxMove > startColumn > maxMove - 1):\n",
    "            return 0\n",
    "        # 向四个方向移动的结果的和\n",
    "        ans = 0\n",
    "        for dx, dy in self.dirc:\n",
    "            ans = (ans + self.findPaths(m, n, maxMove - 1, startRow + dx, startColumn + dy)) % self.mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param m:\n",
    "        :param n:\n",
    "        :param maxMove:\n",
    "        :param startRow:\n",
    "        :param startColumn:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "        mod1 = 10 ** 9 + 7\n",
    "        okCnt = self.getAns(maxMove, startRow, startColumn)\n",
    "        return okCnt % mod1\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def getAns(self, curM, curX, curY):\n",
    "        if curX < 0 or curX > self.m - 1 or curY < 0 or curY > self.n - 1:\n",
    "            return 1\n",
    "        if curM == 0:\n",
    "            return 0\n",
    "        ok1 = self.getAns(curM - 1, curX + 1, curY)\n",
    "        ok2 = self.getAns(curM - 1, curX, curY + 1)\n",
    "        ok3 = self.getAns(curM - 1, curX - 1, curY)\n",
    "        ok4 = self.getAns(curM - 1, curX, curY - 1)\n",
    "        return ok1 + ok2 + ok3 + ok4\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        # dp[i][x][y]：呆在（x,y）这一点，且还剩下i步的方案数\n",
    "        # 转移：dp[i-1][ntx][nty] += dp[i][x][y]\n",
    "        # 边界：如果(x,y)出界且i==0 返回1，否则0\n",
    "        ret = 0\n",
    "        n,m = m,n\n",
    "        dire = [(-1,0),(0,1),(1,0),(0,-1)]\n",
    "        @cache\n",
    "        def dfs(left,x,y):\n",
    "            if left==0:\n",
    "                if x<0 or y<0 or x>=n or y>=m:\n",
    "                    return 1\n",
    "                return 0\n",
    "            if x<0 or y<0 or x>=n or y>=m:\n",
    "                return 1 if left == 0 else 0\n",
    "            res = 0\n",
    "            for a,b in dire:\n",
    "                res = (res + dfs(left-1,x+a,y+b))%MOD\n",
    "            \n",
    "            return res\n",
    "\n",
    "        for i in range(1,maxMove+1):\n",
    "            ret = (ret + dfs(i,startRow,startColumn))%MOD\n",
    "\n",
    "        \n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
